package com.ztom.top100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 有效的括号
 * <p>
 * https://leetcode-cn.com/problems/valid-parentheses/
 *
 * @author ZhangTao
 */
public class Code11IsValid {

    public boolean isValid1(String s) {
        if (s == null || (s.length() & 1) == 1) {
            return false;
        }

        char[] str = s.toCharArray();
        Deque<Character> stack = new LinkedList<>();
        for (char c : str) {
            if (stack.isEmpty()) {
                stack.addLast(c);
            } else if (isValid(stack.peekLast(), c)) {
                stack.pollLast();
            } else {
                stack.addLast(c);
            }
        }
        return stack.isEmpty();
    }

    public boolean isValid(String s) {
        if (s == null || (s.length() & 1) == 1) {
            return false;
        }

        char[] str = s.toCharArray();
        char[] stack = new char[str.length];
        int stackIndex = -1;
        for (char c : str) {
            if (stackIndex == -1) {
                stack[++stackIndex] = c;
            } else if (isValid(stack[stackIndex], c)) {
                stackIndex--;
            } else {
                stack[++stackIndex] = c;
            }
        }
        return stackIndex == -1;
    }

    private boolean isValid(char a, char b) {
        return (a == '(' && b == ')')
                || (a == '[' && b == ']')
                || (a == '{' && b == '}');
    }
}
